package Random;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class _54_SpiralMatrix {


    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix.length == 0 || matrix[0].length == 0) {
            return res;
        }
        int[] dr = new int[]{0, 1, 0, -1};
        int[] dc = new int[]{1, 0, -1, 0};
        int rpos = 0;
        int cpos = 0;
        int pos = 0;//0 is right, 1 is down, 2 is left, 3 is up.
        int count = 1;
        int length = matrix.length;
        int width = matrix[0].length;
        int total = length * width;
        boolean[][] check = new boolean[length][width];
        while (count <= total) {
            res.add(matrix[rpos][cpos]);
            check[rpos][cpos] = true;
            if ((pos == 0 && (cpos + 1 == width || check[rpos][cpos + 1])) ||
                    (pos == 1 && (rpos + 1 == length || check[rpos + 1][cpos])) ||
                    (pos == 2 && (cpos - 1 == -1 || check[rpos][cpos - 1])) ||
                    (pos == 3 && (rpos - 1 == -1 || check[rpos - 1][cpos]))
            ) {

                pos = (pos + 1) % 4;
            }
            rpos += dr[pos];
            cpos += dc[pos];
            count++;
        }
        return res;
    }
}
